INTERESTING LINKS
Puzzles
Mathematics
Blogs
Problems in Issue 11.1
0. The increasing sequence 1, 3, 4, 9, 10, 12, 13… consists of all those positive integers which are powers of 3 or sums of distinct powers of 3. Find the 100th term of the sequence.
1. Consider N petrol bunks on a circular highway. A car is to start with zero petrol from one of the bunks and travel around the circle, returning to its original point. The petrol is distributed among the bunks in such a way that the total amount of petrol available in all the bunks is exactly sufficient for the car to make a single loop of the highway.
Prove that there always exists a choice of the starting bunk such that the car will be able to complete the loop.2. There are N parking slots numbered 1 to N. There are N cars, labeled C1 to CN. Given a sequence {a1, a2,…,aN | 1=< ai <=N; for 1 <= i <= n}, car Ci goes to the slot numbered ai and parks the car there if it is not already occupied, otherwise it parks in the next higher unoccupied slot. It can happen that the car never gets to park at any slot.
Find the number of sequences {a1, a2,…,aN | 1=< ai <=N; for 1 <= i <= n}, such that all cars are parked in some slot.Hints
0. Think about your basics!
1. We're giving you a solution here. We aren't benevolent though; we want you to give us an inductive solution.
Solution: Choose a particular bunk and make the car run (either clockwise or anticlockwise) one full circle. Do this even if petrol quantity is insufficient for one or more segments of the journey (that is, assume negative petrol is allowed for such cases).
Now, identify the petrol bunk at which the car has minimum petrol. This is the one you should start from if you want to fulfill the conditions of the problem. Check (yourself) that if the car starts from that bunk, it will have no problem.
Solutions
PREVIOUS PROBLEMS
In this section, you can browse through the problems that have appeared in previous issues of InsIghT, get hints and see the solutions.